package algorithms;
import java.util.Collections;

import game.AbstractOthelloPosition;
import game.OthelloAction;
import search.OthelloSearchNode;

public class OthelloAlgorithm implements OthelloAlgorithmInterface {
	private static final int AB_FIRST_PASS = 6;
	private static final int INF = (int) Math.pow(10, 9);
	private OthelloEvaluatorInterface _evaluator;
	private int _maxdepth;

	public OthelloAlgorithm(int maxDepth, OthelloEvaluatorInterface evaluator){
		_evaluator = evaluator;
		_maxdepth = maxDepth;
	}

	@Override
	public void setEvaluator(OthelloEvaluatorInterface evaluator) {
		_evaluator = evaluator;
	}

	@Override
	public void setSearchDepth(int depth) {
		_maxdepth = depth;
	}

	@Override
	public OthelloAction evaluate(AbstractOthelloPosition position) {
		OthelloSearchNode head = new OthelloSearchNode(0, position);
		int depth = checkSize(head);
		int score = alphaBeta(head, -INF, INF, depth, true);
		OthelloAction bestAction = head.getActionFromUtility(score);
		if(bestAction == null){
			OthelloAction pass = new OthelloAction(0, 0);
			pass.setPassMove(true);
			return pass;
		}
		return bestAction;
	}

	private int checkSize(OthelloSearchNode head) {
		if(head.expandNode()) {
			int nbChildren = head.getChilds().size();
			if(nbChildren >= 7) {
				return 5;
			}
		}
		return _maxdepth;
	}

	/**
	 * Alpha beta search algorithm
	 * @param node starting node for search
	 * @param alpha alpha bound
	 * @param beta beta bound
	 * @param depth maximal depth
	 * @param maximize set to true if the node is a maximizing node, false otherwise.
	 * @return the best utility value in the tree
	 */
	private int alphaBeta(OthelloSearchNode node, int alpha, int beta, int depth, boolean maximize){
		if(node.getLevel() == depth){
			node.setUtility(_evaluator.evaluate(node.getPosition()));
			return node.getUtility();
		}
		int value;
		if(!maximize){
			value = INF;
			if(!node.expandNode()) {
				node.setUtility(_evaluator.evaluate(node.getPosition()));
				return node.getUtility();
			}
			for(OthelloSearchNode c : node.getChilds()){
				value = Math.min(value, alphaBeta(c, alpha, beta, depth, !maximize));
				if(alpha >= value){
					node.setUtility(value);
					return value;
				}
				beta = Math.min(beta, value);
			}
		}else{
			value = -INF;
			if(!node.expandNode()) {
				node.setUtility(_evaluator.evaluate(node.getPosition()));
				return node.getUtility();
			}
			for(OthelloSearchNode c : node.getChilds()){
				value = Math.max(value, alphaBeta(c, alpha, beta, depth, !maximize));
				if(value >= beta){
					node.setUtility(value);
					return value;
				}
				alpha = Math.max(alpha, value);
			}
		}
		node.setUtility(value);
		return value;
	}
}
